﻿//Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).


using System;
using System.Collections.Generic;

public class QuickSortAlgorithm
{
    static void Main()
    {
        Console.Write("Enter the number of elements of the array: ");
        int length = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} elements of the array", length);
        List<int> array = new List<int>(length);
        for (int i = 0; i < array.Capacity; i++)
        {
            array.Add(int.Parse(Console.ReadLine()));
        }
        Console.WriteLine();
        List<int> result = QuickSort(array);
        Console.WriteLine("Sorted array is:");
        for (int i = 0; i < result.Count; i++)
        {
            if (i == 0)
            {
                Console.Write("{{{0}, ", result[i]);
            }
            else if (i == result.Count - 1)
            {
                Console.Write("{0}}}\n", result[i]);
            }
            else
            {
                Console.Write("{0}, ", result[i]);
            }
        }
    }

    private static List<int> QuickSort(List<int> array)
    {
        if (array.Count <= 1)
        {
            return array;
        }

        int pivot = array[array.Count / 2];
        List<int> left = new List<int>();
        List<int> right = new List<int>();

        for (int i = 0; i < array.Count; i++)
        {
            if (i != (array.Count / 2))
            {
                if (array[i] <= pivot)
                {
                    left.Add(array[i]);
                }
                else
                {
                    right.Add(array[i]);
                }
            }
        }

        return SortedArrays(QuickSort(left), QuickSort(right), pivot);
    }

    private static List<int> SortedArrays(List<int> left, List<int> right, int pivot)
    {
        List<int> result = new List<int>();

        for (int i = 0; i < left.Count; i++)
        {
            result.Add(left[i]);
        }

        result.Add(pivot);

        for (int i = 0; i < right.Count; i++)
        {
            result.Add(right[i]);
        }

        return result;
    }
}